#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    // 迭代
    ListNode *iterate(ListNode *head);
    // 递归
    ListNode *recursion(ListNode *head);
};

ListNode *Solution::iterate(ListNode *head)
{
    // 设立当前结点 prev next用于保存
    ListNode *curr = head, *next, *prev = nullptr;
    // curr作为循环变量
    while (curr != nullptr)
    {
        // 保存
        next = curr->next;
        // 赋值
        curr->next = prev;
        prev = curr; // 一开始为null 后面为上一次的curr
        // 遍历
        curr = next;
    }
    return prev;
}

ListNode *Solution::recursion(ListNode *head)
{
    // 特殊情况 链表为空或者只有一个结点 同时为迭代的首次返回
    if (head == nullptr || head->next == nullptr)
    {
        return head;
    }
    // 防止结点丢失 从tail开始迭代
    ListNode *newhead = recursion(newhead->next);
    // 迭代本体 从倒数第二次结点往前开始执行
    head->next->next = head;
    head->next = nullptr;
    return newhead;
}